SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Turing-complet</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Turing-complet</h1>

</header>

</div>

En <a href="Informatique" title="Informatique">informatique</a> et en <a href="Logique" title="Logique">logique</a>, un <a href="Syst%C3%A8me_formel" title="Système formel">système formel</a> est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-complete<a href="#cite_note-1">[1]</a>) s’il possède un <a href="Th%C3%A9orie_de_la_calculabilit%C3%A9" title="Théorie de la calculabilité">pouvoir expressif</a> au moins équivalent à celui des <a href="Machine_de_Turing" title="Machine de Turing">machines de Turing</a>. Dans un tel système, il est donc possible de <a href="Programmation_informatique" title="Programmation informatique">programmer</a> n'importe quelle machine de Turing.

Cette notion est rendue pertinente par la <a href="Th%C3%A8se_de_Church" title="Thèse de Church">thèse de Church</a>, qui postule l’existence d’une notion naturelle de calculabilité. Ainsi, le pouvoir expressif des machines de Turing coïncide avec celui des <a href="Fonction_r%C3%A9cursive" title="Fonction récursive">fonctions récursives</a>, du <a href="Lambda-calcul" title="Lambda-calcul">lambda calcul</a>, ou encore des <a href="Machine_%C3%A0_compteurs" title="Machine à compteurs">machines à compteurs</a>.

Bien que certains modèles de calcul, appelés des <a href="Hypercalcul" title="Hypercalcul">hypercalculs</a>, soient strictement plus expressifs que les machines de Turing, ces modèles sont des objets de spéculation (requérant par exemple d’effectuer une infinité d’opérations, ou de calculer sur l’ensemble des <a href="Nombre_r%C3%A9el" title="Nombre réel">nombres réels</a>) et l’on ignore s’ils sont physiquement réalisables.

Dans ces conditions, la thèse de Church <a href="Conjecture" title="Conjecture">conjecture</a> l’universalité du modèle de calcul des machines de Turing : tout système Turing-complet serait en fait équivalent aux machines de Turing.

<div class="mw-heading mw-heading2"><h2 id="Langages_de_programmation_Turing-complets">Langages de programmation Turing-complets</h2></div>

De même qu'un modèle de calcul, un <a href="Langage_informatique" title="Langage informatique">langage informatique</a> est dit Turing-complet s'il permet de représenter toutes les <a href="Fonction_r%C3%A9cursive" title="Fonction récursive">fonctions calculables</a> au sens de <a href="Alan_Turing" title="Alan Turing">Turing</a> et <a href="Alonzo_Church" title="Alonzo Church">Church</a> (nonobstant la <a href="Finitude" title="Finitude">finitude</a> de la <a href="M%C3%A9moire_(informatique)" title="Mémoire (informatique)">mémoire</a> des ordinateurs<a href="#cite_note-2">[note 1]</a>).

Certains auteurs prennent cette propriété pour définition d’un <a href="Langage_de_programmation" title="Langage de programmation">langage de programmation</a><a href="#cite_note-3">[2]</a>,<a href="#cite_note-4">[3]</a>, mais d'autres définitions peuvent être choisies<a href="#cite_note-5">[4]</a>.

Les langages de programmation usuels (<a href="C_(langage)" title="C (langage)">C</a>, <a href="Java_(langage)" title="Java (langage)">Java</a>…) sont Turing-complets car ils possèdent tous les ingrédients nécessaires à la simulation d'une machine de Turing universelle (compter, comparer, lire, écrire, etc.)<a href="#cite_note-6">[5]</a>. Le langage <a href="C%2B%2B" title="C++">C++</a> est également Turing-complet, et le sous-ensemble permettant la <a href="G%C3%A9n%C3%A9ricit%C3%A9" title="Généricité">programmation générique</a> (<a href="Template_(programmation)" title="Template (programmation)">templates</a>) l'est aussi[réf. nécessaire].

Le langage <a href="SQL" class="mw-redirect" title="SQL">SQL</a>, à l'origine non complet au sens de Turing, l'est devenu avec la norme SQL:1999 lui permettant d'écrire des requêtes <a href="Fonction_r%C3%A9cursive" title="Fonction récursive">récursives</a>[réf. nécessaire].

Le langage <a href="LaTeX" title="LaTeX">LaTeX</a> (issu du <a href="TeX" title="TeX">TeX</a>), destiné à la composition de documents, est également Turing-complet<a href="#cite_note-7">[6]</a>.

Le langage <a href="HTML" class="mw-redirect" title="HTML">HTML</a> seul n'est pas Turing-complet, cependant il a été prouvé que le langage <a href="Feuilles_de_style_en_cascade" title="Feuilles de style en cascade">CSS</a> (en version 3) permet de construire l'<a href="Automate_cellulaire#Les_automates_cellulaires_les_plus_simples" title="Automate cellulaire">automate cellulaire élémentaire de code 110</a> (voir Rule 110 <a href="https://en.wikipedia.org/wiki/Rule_110" class="extiw external" title="en:Rule 110">(en)</a><a href="#cite_note-8">[7]</a>), connu pour être universel au sens de Turing. Ces deux langages étant souvent indissociables, on peut conclure que le HTML+CSS est Turing-complet, et cette association en fait donc théoriquement un langage de programmation.

Un langage Turing-complet hérite des caractéristiques d'une machine de Turing. Par exemple, le <a href="Probl%C3%A8me_de_l'arr%C3%AAt" title="Problème de l'arrêt">problème de l'arrêt</a> est <a href="Ind%C3%A9cidable" class="mw-redirect" title="Indécidable">indécidable</a>, donc il est impossible d'écrire un programme qui dit si un programme arbitraire qu'on lui fournit se termine ou non.

<div class="mw-heading mw-heading2"><h2 id="Langages_qui_ne_sont_pas_Turing-complets">Langages qui ne sont pas Turing-complets</h2></div>

Certains <a href="Langage_d%C3%A9di%C3%A9" title="Langage dédié">langages dédiés</a> au traitement de problèmes spécifiques ne sont pas Turing-complets. <a href="Syst%C3%A8me_F" title="Système F">Système F</a>, un formalisme de lambda calcul en est un exemple. Par ailleurs — par conception —, les langages totaux <a href="https://en.wikipedia.org/wiki/Total_functional_programming" class="extiw external" title="en:Total functional programming">(en)</a>, où tous les calculs se terminent nécessairement (comme le langage <a href="Gallina" title="Gallina">Gallina</a> de l'assistant de preuve <a href="Rocq_(logiciel)" title="Rocq (logiciel)">Rocq</a>), ne sont pas non plus Turing-complets. Cependant, ces derniers sont en pratique capables de calculer tout ce qui est intéressant<a href="#cite_note-9">[8]</a>,<a href="#cite_note-10">[9]</a>, en d'autres termes ils peuvent mettre en œuvre toutes les fonctions dont nous pourrions avoir besoin dans la vie pratique ; les calculs qui leur échappent, soit ont une complexité au-delà de l'imaginable et du réalisable, soit ne se terminent pas. La compilation doit alors démontrer la terminaison des programmes, ou nécessiter une interaction avec le programmeur pour certaines démonstrations, mais c'est le prix à payer pour une qualité de code qui est correcte par construction.

<div class="mw-heading mw-heading2"><h2 id="Exemples_en_dehors_des_langages_de_programmation">Exemples en dehors des langages de programmation</h2></div>

Certains jeux et logiciels présentent une complétude de Turing de manière fortuite, sans que leurs concepteurs l'aient intentionnellement recherchée ou anticipée.

<ul><li><a href="Slaves_to_Armok_II%3A_Dwarf_Fortress" class="mw-redirect" title="Slaves to Armok II: Dwarf Fortress">Dwarf Fortress</a><a href="#cite_note-themarysue-11">[10]</a></li>

<li><a href="Magic_%3A_L'Assembl%C3%A9e" title="Magic : L'Assemblée">Magic : L'Assemblée</a><a href="#cite_note-12">[11]</a></li>

<li><a href="Cities%3A_Skylines" title="Cities: Skylines">Cities: Skylines</a><a href="#cite_note-13">[12]</a></li>

<li><a href="D%C3%A9mineur" class="mw-disambig" title="Démineur">Démineur</a> avec grille infinie<a href="#cite_note-14">[13]</a></li></ul>

<ul><li>Le <a href="Jeu_de_la_vie" title="Jeu de la vie">jeu de la vie</a>, un <a href="Automate_cellulaire" title="Automate cellulaire">automate cellulaire</a><a href="#cite_note-15">[14]</a></li>

<li><a href="PowerPoint" class="mw-redirect" title="PowerPoint">PowerPoint</a><a href="#cite_note-16">[15]</a></li>

<li><a href="Habbo" title="Habbo">Habbo</a><a href="#cite_note-17">[16]</a></li>

<li>Microsoft Excel<a href="#cite_note-19">[18]</a></li>

<li><a href="Opus_Magnum" title="Opus Magnum">Opus Magnum</a><a href="#cite_note-20">[19]</a></li></ul>

Dans certains cas, l'intégration d'une propriété de complétude de Turing est intentionnelle, en raison de la capacité à implémenter des portes logiques et à contrôler un circuit électrique, constituant ainsi une composante essentielle du jeu :

<ul><li><a href="Minecraft" title="Minecraft">Minecraft</a><a href="#cite_note-21">[20]</a></li>

<li><a href="Factorio" title="Factorio">Factorio</a><a href="#cite_note-22">[21]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Articles_connexes">Articles connexes</h2></div>

<ul><li><a href="Boucle_infinie" title="Boucle infinie">Boucle infinie</a></li>

<li><a href="Th%C3%A9or%C3%A8me_de_Rice" title="Théorème de Rice">Théorème de Rice</a></li>

<li><a href="Calculabilit%C3%A9" class="mw-redirect" title="Calculabilité">Théorie de la Calculabilité</a></li>

<li><a href="Th%C3%A8se_de_Church" title="Thèse de Church">Thèse de Church</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes_et_références">Notes et références</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Notes">Notes</h3></div>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Un ordinateur a une mémoire finie, le modèle de calcul des <a href="Machine_de_Turing" title="Machine de Turing">machines de Turing</a> a une mémoire illimitée.

</li>

</ol></div>

</div>

<div class="mw-heading mw-heading3"><h3 id="Références">Références</h3></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> <a href="Bureau_de_la_traduction" title="Bureau de la traduction">Bureau de la traduction</a>, <a rel="nofollow" class="external text" href="http://www.btb.termiumplus.gc.ca/tpv2alpha/alpha-fra.html?lang=fra&srchtxt=COMPLET%20SENS%20TURING">fiche de la banque de données TERMIUM Plus</a>, sur <a href="TERMIUM_Plus" title="TERMIUM Plus">termiumplus.gc.ca</a>, <time class="nowrap" datetime="2017-02-02" data-sort-value="2017-02-02">2 février 2017</time> (consulté le <time class="nowrap" datetime="2019-05-23" data-sort-value="2019-05-23">23 mai 2019</time>)

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> John C. Mitchell, <cite class="italique" lang="en">Concepts in Programming Languages</cite>, <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, <time>2003</time> (<a rel="nofollow" class="external text" href="https://books.google.ca/books?id=7Uh8XGfJbEIC&pg=PA14">lire en ligne</a>), <abbr class="abbr" title="page">p.</abbr> 14<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Concepts+in+Programming+Languages&rft.pub=Cambridge+University+Press&rft.aulast=Mitchell&rft.aufirst=John+C.&rft.date=2003&rft.pages=14&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATuring-complet"> : <blockquote>« The fact that all standard programming languages express precisely the class of partial recursive functions is often summarized by the statement that all programming languages are Turing complete. »</blockquote>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Bruce J. MacLennan, <cite class="italique" lang="en">Principles of Programming Languages</cite>, <a href="Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>, <time>1999</time>, Introduction: What is a programming language?<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Principles+of+Programming+Languages&rft.pub=Oxford+University+Press&rft.aulast=MacLennan&rft.aufirst=Bruce+J.&rft.date=1999&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATuring-complet"> : <blockquote>« A programming language is a language that is intended for the expression of computer programs and that is capable of expressing any computer program. This is not a vague notion. There is a precise theorical way of determining whether a computer language can be used to express any program, namely, by showing that it is equivalent to a universal Turing machine. »</blockquote>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> « <a rel="nofollow" class="external text" href="http://programmers.stackexchange.com/questions/172979/are-non-turing-complete-languages-considered-programming-languages-at-all"><cite style="font-style:normal;" lang="en">Are non Turing-complete languages considered programming languages at all?</cite></a> », sur <a href="Stack_Exchange_Network" title="Stack Exchange Network">Stack Exchange</a> <div style="margin-left:2em; line-height:1.5;">À la question posée, une réponse sélectionnée considère que la Turing-complétude n’est pas requise pour considérer un langage comme langage de programmation.</div>.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> Exemple de mise en œuvre d'une machine de Turing en C : <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Juan Pablo Rinaldi (juampi), « <a rel="nofollow" class="external text" href="https://github.com/juampi/turing"><cite style="font-style:normal;" lang="en">An implementation of a Turing Machine in C</cite></a> », sur <a href="GitHub" title="GitHub">GitHub</a>, <time class="nowrap" datetime="2014-01-13" data-sort-value="2014-01-13">13 janvier 2014</time> (consulté le <time class="nowrap" datetime="2019-05-21" data-sort-value="2019-05-21">21 mai 2019</time>).

</li>

<li id="cite_note-7"><a href="#cite_ref-7">↑</a> « <a rel="nofollow" class="external text" href="https://fr.sharelatex.com/blog/2012/04/24/latex-is-more-powerful-than-you-think.html"><cite style="font-style:normal;">LaTeX is More Powerful than you Think - Computing the Fibonacci Numbers and Turing Completeness - ShareLaTeX, Éditeur LaTeX en ligne</cite></a> », sur fr.sharelatex.com (consulté le <time class="nowrap" datetime="2017-06-02" data-sort-value="2017-06-02">2 juin 2017</time>).

</li>

<li id="cite_note-8"><a href="#cite_ref-8">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Eli & Jonas, « <a rel="nofollow" class="external text" href="https://accodeing.com/blog/2015/css3-proven-to-be-turing-complete"><cite style="font-style:normal;" lang="en">CSS3 proven to be "Turing-complete"</cite></a> », sur Accodeing to you (consulté le <time class="nowrap" datetime="2019-05-17" data-sort-value="2019-05-17">17 mai 2019</time>).

</li>

<li id="cite_note-9"><a href="#cite_ref-9">↑</a> « <a rel="nofollow" class="external text" href="http://lambda-the-ultimate.org/node/2846"><cite style="font-style:normal;">On the importance of Turing completeness</cite></a> », sur Lambda the Ultimate <a href="https://en.wikipedia.org/wiki/Lambda_the_Ultimate" class="extiw external" title="en:Lambda the Ultimate">(en)</a>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">↑</a> Benjamin Werner, « <cite style="font-style:normal">Sets in Types, Types in Sets</cite> », Proceedings of TACS'97,‎ <time>1997</time><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Sets+in+Types%2C+Types+in+Sets&rft.jtitle=Proceedings+of+TACS%2797&rft.aulast=Werner&rft.aufirst=Benjamin&rft.date=1997&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATuring-complet">.

</li>

<li id="cite_note-themarysue-11"><a href="#cite_ref-themarysue_11-0">↑</a> Andrew Cedotal, « <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150627102458/http://www.themarysue.com/dwarf-fortress-turing-machine-computer/">Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine</a> », sur www.themarysue.com, <time class="nowrap" datetime="2010-04-16" data-sort-value="2010-04-16">16 avril 2010</time> (version du <time class="nowrap" datetime="2015-06-27" data-sort-value="2015-06-27">27 juin 2015</time> sur <a href="Internet_Archive" title="Internet Archive">Internet Archive</a>).

</li>

<li id="cite_note-12"><a href="#cite_ref-12">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Alex Churchill, « <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190507120026/https://arxiv.org/abs/1904.09828">Magic: The Gathering is Turing Complete</a> », sur Cornell University, <time class="nowrap" datetime="2019-04-23" data-sort-value="2019-04-23">23 avril 2019</time> (version du <time class="nowrap" datetime="2019-05-07" data-sort-value="2019-05-07">7 mai 2019</time> sur <a href="Internet_Archive" title="Internet Archive">Internet Archive</a>).

</li>

<li id="cite_note-13"><a href="#cite_ref-13">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Daniel Bali, « <a rel="nofollow" class="external text" href="https://medium.com/@balidani/cities-skylines-is-turing-complete-e5ccf75d1c3a"><cite style="font-style:normal;" lang="en">Cities: Skylines is Turing Complete</cite></a> », sur Medium, <time class="nowrap" datetime="2019-07-15" data-sort-value="2019-07-15">15 juillet 2019</time> (consulté le <time class="nowrap" datetime="2025-10-15" data-sort-value="2025-10-15">15 octobre 2025</time>)

</li>

<li id="cite_note-14"><a href="#cite_ref-14">↑</a> Richard Kaye, « <cite style="font-style:normal">Minesweeper is NP-complete</cite> », The Mathematical Intelligencer, <abbr class="abbr" title="volume">vol.</abbr> 22, <abbr class="abbr" title="numéro">no</abbr> 2,‎ <time class="nowrap" datetime="2000-03" data-sort-value="2000-03">mars 2000</time>, <abbr class="abbr" title="pages">p.</abbr> 9–15 (<a href="International_Standard_Serial_Number" title="International Standard Serial Number">ISSN</a> <a rel="nofollow" class="external text" href="https://portal.issn.org/resource/issn/0343-6993">0343-6993</a>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1007/bf03025367">10.1007/bf03025367</a>, <a rel="nofollow" class="external text" href="https://doi.org/10.1007/bf03025367">lire en ligne</a>, consulté le <time class="nowrap" datetime="2025-09-17" data-sort-value="2025-09-17">17 septembre 2025</time>)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Minesweeper+is+NP-complete&rft.jtitle=The+Mathematical+Intelligencer&rft.issue=2&rft.aulast=Kaye&rft.aufirst=Richard&rft.date=2000-03&rft.volume=22&rft.pages=9%E2%80%9315&rft.issn=0343-6993&rft_id=info%3Adoi%2F10.1007%2Fbf03025367&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATuring-complet">

</li>

<li id="cite_note-15"><a href="#cite_ref-15">↑</a> Paul Rendell, « <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090708160241/http://rendell-attic.org/gol/tm.htm">A Turing Machine in Conway's Game of Life</a> », sur rendell-attic.org, <time class="nowrap" datetime="2005-01-12" data-sort-value="2005-01-12">12 janvier 2005</time> (version du <time class="nowrap" datetime="2009-07-08" data-sort-value="2009-07-08">8 juillet 2009</time> sur <a href="Internet_Archive" title="Internet Archive">Internet Archive</a>).

</li>

<li id="cite_note-16"><a href="#cite_ref-16">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Tom Wildenhain, « <a rel="nofollow" class="external text" href="https://www.andrew.cmu.edu/user/twildenh/PowerPointTM/Paper.pdf"><cite style="font-style:normal; color:var(--color-link-red, #d73333);" lang="en">On the Turing Completeness of MS Powerpoint</cite></a> »(<a rel="nofollow" class="external text" href="https://web.archive.org/web/*/https://www.andrew.cmu.edu/user/twildenh/PowerPointTM/Paper.pdf">Archive.org</a> • <a rel="nofollow" class="external text" href="https://archive.wikiwix.com/cache/?url=https://www.andrew.cmu.edu/user/twildenh/PowerPointTM/Paper.pdf">Wikiwix</a> • <a rel="nofollow" class="external text" href="https://archive.is/https://www.andrew.cmu.edu/user/twildenh/PowerPointTM/Paper.pdf">Archive.is</a> • <a rel="nofollow" class="external text" href="https://webcache.googleusercontent.com/search?hl=fr&q=cache:https://www.andrew.cmu.edu/user/twildenh/PowerPointTM/Paper.pdf">Google</a> • Que faire ?), sur andrew.cmu.edu, <time class="nowrap" datetime="2017-03-16" data-sort-value="2017-03-16">16 mars 2017</time> (consulté le <time class="nowrap" datetime="2020-07-10" data-sort-value="2020-07-10">10 juillet 2020</time>).

</li>

<li id="cite_note-17"><a href="#cite_ref-17">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Habbo (@Habbo), « <a rel="nofollow" class="external text" href="https://twitter.com/Habbo/status/1325785673304043522"><cite style="font-style:normal;" lang="en">We know that there are some talented Habbos out there but this one might just take the cake! One of our players @sirjonasxx took on the challenge of creating a functioning Turing machine in-game and they SUCCEEDED! Let’s check it out.</cite></a> », sur <a href="Twitter" class="mw-redirect" title="Twitter">Twitter</a>, <time class="nowrap" datetime="2020-11-09" data-sort-value="2020-11-09">9 novembre 2020</time> (consulté le <time class="nowrap" datetime="2020-11-30" data-sort-value="2020-11-30">30 novembre 2020</time>)

</li>

<li id="cite_note-18"><a href="#cite_ref-18">↑</a> « <a rel="nofollow" class="external text" href="https://www.twitlonger.com/show/n_1sqrh1m"><cite style="font-style:normal;">TwitLonger — When you talk too much for Twitter</cite></a> », sur twitlonger.com (consulté le <time class="nowrap" datetime="2021-11-28" data-sort-value="2021-11-28">28 novembre 2021</time>).

</li>

<li id="cite_note-19"><a href="#cite_ref-19">↑</a> <cite style="font-style:normal">« Chapter 1: Formulas in Excel »</cite>, dans <cite class="italique">Microsoft Excel Functions and Formulas</cite>, De Gruyter, <time class="nowrap" datetime="2024-03-11" data-sort-value="2024-03-11">11 mars 2024</time>, 1–36 <abbr class="abbr" title="pages">p.</abbr> (<a href="International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> 978-1-68392-852-2, <a rel="nofollow" class="external text" href="https://doi.org/10.1515/9781683928522-003">lire en ligne</a>)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.btitle=Microsoft+Excel+Functions+and+Formulas&rft.atitle=Chapter+1%3A+Formulas+in+Excel&rft.pub=De+Gruyter&rft.date=2024-03-11&rft.tpages=1%E2%80%9336&rft.isbn=978-1-68392-852-2&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATuring-complet">

</li>

<li id="cite_note-20"><a href="#cite_ref-20">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Brendan Caldwell, « <cite style="font-style:normal" lang="en">Opus Magnum player makes an alchemical computer</cite> », Rock, Paper, Shotgun,‎ <time class="nowrap" datetime="2017-11-20" data-sort-value="2017-11-20">20 novembre 2017</time> (<a rel="nofollow" class="external text" href="https://www.rockpapershotgun.com/opus-magnum-player-makes-computer">lire en ligne</a>, consulté le <time class="nowrap" datetime="2025-09-17" data-sort-value="2025-09-17">17 septembre 2025</time>)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Opus+Magnum+player+makes+an+alchemical+computer&rft.jtitle=Rock%2C+Paper%2C+Shotgun&rft.aulast=Caldwell&rft.aufirst=Brendan&rft.date=2017-11-20&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATuring-complet">

</li>

<li id="cite_note-21"><a href="#cite_ref-21">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Gunivers, « <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=itgPhvTMSZQ"><cite style="font-style:normal;" lang="en">Data Pack - Universal Turing Machine</cite></a> », sur <a href="YouTube" title="YouTube">YouTube</a>, <time class="nowrap" datetime="2019-07-17" data-sort-value="2019-07-17">17 juillet 2019</time> (consulté le <time class="nowrap" datetime="2020-05-06" data-sort-value="2020-05-06">6 mai 2020</time>).

</li>

<li id="cite_note-22"><a href="#cite_ref-22">↑</a> <abbr class="abbr indicateur-format format-vidéo" title="Vidéo au format MPEG, AVI...">[vidéo]</abbr> « <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=brYDcNxyU_0"><cite style="font-style:normal;">Factorio turing machine with No Combinators</cite></a> », IQuick 143, <time class="nowrap" datetime="2019-01-02" data-sort-value="2019-01-02">2 janvier 2019</time>, 6:48 <abbr class="abbr" title="minute">min</abbr> (consulté le <time class="nowrap" datetime="2025-05-30" data-sort-value="2025-05-30">30 mai 2025</time>)

</li>

</ol></div>

</div>

<div class="mw-heading mw-heading2"><h2 id="Annexes">Annexes</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Articles_connexes_2">Articles connexes</h3></div>

<ul><li><a href="Alan_Turing" title="Alan Turing">Alan Turing</a></li>

<li><a href="Th%C3%A8se_de_Church" title="Thèse de Church">Thèse de Church</a></li></ul>

<ul id="bandeau-portail" class="bandeau-portail"><li> Portail de l'informatique théorique </li> <li> Portail de la logique </li> </ul></div><div><div class="zim-footer">

Cet article est issu de <a class="external text" title="Dernière modification le 2025-10-17" href="https://fr.wikipedia.org/wiki/?title=Turing-complet&oldid=229844401">Wikipédia</a>. Sauf mention contraire, le texte est disponible sous <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">Creative Commons Attribution-Share Alike 4.0</a>. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

</div>

</div></div>

</div>

</main>

</div>

</body></html>